МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Структура даних СТЕК
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 3
з дисципліни
" Програмування. Частина III.
Структури даних та алгоритми "
для студентів напрямку
6.0915 “Комп’ютерна інженерія”
Львів – 2008
Методичні вказівки до лабораторної роботи "Структура даних СТЕК" з дисципліни “Програмування. Частина IIІ. Структури даних та алгоритми" для підготовки студентів напрямку 6.0915 “Комп’ютерна інженерія” / Укл. Т.А.Лисак – Львів: Видавництво НУ “Львівська політехніка”, 2008 – 27 с.
Укладач: Лисак Т.А., ст. викладач каф.ЕОМ
Відповідальний
за випуск: Мельник А.О., д-р техн. наук, проф.
Рецензенти: Опир Ю.М., ст. викладач каф.ЕОМ
Юрчак І.Ю., доцент кафедри САПР, к.т.н.
1. МЕТА РОБОТИ
Вивчення фундаментальної абстрактної структури даних - стека. Набуття практичних навичок побудови стека, дослідження динаміки його вмісту та використання стеків для розв'язання прикладних задач.
2. ТЕОРЕТИЧНІ ВІДОМОСТІ
Стек - динамічна структура даних, що представляє собою впорядкований набір елементів, у якій додавання нових елементів і видалення існуючих відбувається з одного кінця, який називається вершиною стека. Згідно визначення, елементи вилучаються зі стека в порядку, зворотному їхньому додаванню в цю структуру, тобто діє принцип LIFO (Last In, Fist Out – останнім прийшов, першим вийшов). Уявимо собі стопку тарілок. Нижня тарелка із цієї стопки буде використана останньою, а верхня тарілка, яка була покладена в стопку останньою, буде використана першою.
Стеки широко використовуються в системному програмному забезпеченні, включаючи компілятори і інтерпретатори.
Найбільш наочним прикладом організації стека служить дитяча пірамідка, де додавання й зняття кілець здійснюється саме відповідно до визначення стека.
Історично склалося так, що дві основні операції для стека - помістити в стек і вилучити зі стека - одержали назву відповідно "заштовхнути" і "виштовхнути". Тому для реализации стека необхідно створити дві функції: "push" (заштовхнути), що поміщає елемент у вершину стека, і "pop" (виштовхнути), що вилучає з вершини стека значення. Необхідно також передбачити певну область у пам'яті, де фактично буде зберігатися стек. Для цього можна використати масив або можна виділити область пам'яті, використовуючи засіб динамічного розпреділення пам'яті.
Приклад 1:
Нехай задана послідовність: 7 , 5 , 9 , 2 . Непарні числа цієї послідовності додаються у стек, а кожне парне число вилучає зі стеку один елемент.
Нижче показана динаміка вмісту стека під час обробки заданої послідовності:
Порожній стек
Елементи вхідної послідовності
7
5
9
2
Data[4]
Data[3]
Data[2]
Data[1]
Used(
Data[0]
Data[4]
Data[3]
Data[2]
Used(
Data[1]
7
Data[0]
Data[4]
Data[3]
Used(
Data[2]
5
Data[1]
7
Data[0]
Data[4]
Used(
Data[3]
9
Data[2]
5
Data[1]
7
Data[0]
Data[4]
Data[3]
Used(
Data[2]
5
Data[1]
7
Data[0]
Функції :
push(7);
push(5);
push(9);
top(); pop();
Оскільки стек - це важлива абстракція даних, у стандартній бібліотеці С++ передбачений клас stack, для використання якого потрібно включити заголовочний файл:
#include <stack>
Повний набір стандартних операцій роботи зі стеком показаний у таблиці:
Операція
Дія
empty()
Повертає true, якщо стек порожній, і false у противному випадку
sіze()
Повертає кількість елементів у стеку
pop()
Видаляє елемент із вершини стека, але не повертає його значення
top()
Повертає значення елемента з вершини стека, але не видаляє його
push(іtem)
Поміщає новий елемент у стек
У наведеній програмі показані приклади використання цих операцій:
#include <stack>
#include <iostream>
int main()
{
const int ia_size = 10;
int ia[ia_size]={0, 1, 2, 3,...
